class Solution {
public:
    bool LFfind(TreeNode* root, TreeNode* n)
    {
        if (root == nullptr)
            return false;
        if (root->val == n->val)
        {
            return true;
        }
        else
        {
            return LFfind(root->left, n) || LFfind(root->right, n);
        }

    }
    char find(TreeNode* root, TreeNode* n)
    {
        if (root->val == n->val)
        {
            return 'T';
        }
        if (LFfind(root->left, n))
        {
            return 'L';
        }
        else
        {
            return 'R';
        }
        return 'T';
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        char fp = find(root, p);
        char fq = find(root, q);
        if (fp != fq)
        {
            return root;
        }
        if (fp == 'L' && fq == 'L')
        {
            return lowestCommonAncestor(root->left, p, q);
        }
        if (fp == 'R' && fq == 'R')
        {
            return lowestCommonAncestor(root->right, p, q);
        }
        return nullptr;
    }
};